﻿public class Solution
{
    private IList<IList<int>> result = new List<IList<int>>();
    private IList<int> path = new List<int>();
    
    public IList<IList<int>> PermuteUnique(int[] nums)
    {
        bool[] used = new bool[nums.Length];
        Array.Sort(nums);
        trackbacking(nums, used);
        return result;
    }

    private void trackbacking(int[] nums, bool[] used)
    {
        if (path.Count == nums.Length)
        {
            result.Add(new List<int>(path));
            return;
        }

        for (int i = 0; i < nums.Length; i++)
        {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;

            used[i] = true;
            path.Add(nums[i]);
            trackbacking(nums, used);
            path.RemoveAt(path.Count-1);
            used[i] = false;
        }
    }

    public static void Main(string[] args)
    {
        int[] nums = [1, 1, 2];
        Solution solution = new Solution();
        IList<IList<int>> result = solution.PermuteUnique(nums);

        foreach (IList<int> res in result)
        {
            foreach (int r in res)
            {
                Console.Write($"{r} ");
            }
            Console.WriteLine();
        }
    }
}